//
//  Sort.swift
//  ArithmeticWithSwift
//
//  Created by 神州锐达 on 2018/9/26.
//  Copyright © 2018年 onePiece. All rights reserved.
//

import Foundation

struct MySort {
    //排序
    //常见的主要有7种。冒泡排序、插入排序、选择排序、堆排序、归并排序、快速排序、桶排序。
    
    //时间复杂度：在计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间，通常用大O符号表示。
    
    //关于这7种排序算法的时间复杂度依次为：冒泡排序 = 插入排序 = 选择排序 > 堆排序 = 归并排序 = 快速排序 > 桶排序。
    
    //排序算法稳定性:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
    
    //1.冒泡排序（稳定）
    //冒泡排序(Bubble Sort)顾名思义就像鱼儿在水底吐出的气泡，从底部会慢慢的漂浮到水面逐渐变大。代码层面表示就是序列中的元素，一步步的向着序列的一侧进行移动，最后达到我们希望的排序效果。
    
    func bubbleSort(_ array: inout [Int]) -> [Int]? {
        //    i表示数组中依次比较的总次数
        for i in 0..<array.count {
            for j in 0..<array.count - i - 1{
                if array[j] > array[j+1]{
                    //                交换数据
                    let temp = array[j]
                    array[j] = array[j+1]
                    array[j+1] = temp
                    
                }
            }
        }
        return array
    }
    
    /*
     注解：
     
     1:每一次外层i的遍历，都会选出未排序数组中的最大值，放到右侧并固定位置。
     
     2:每一次j的遍历，会根据左右元素进行大小比较，若左边数据较大则进行交换。
     */
    
    
    //2.插入排序（稳定）
    //插入排序(Insert Sort)是对已经有序的序列插入新的元素，使其序列仍然有序。
    
    func insertSort(_ array: inout [Int]) -> [Int]? {
        for i in 1..<array.count {
            let temp = array[i]
            //        从之前已经排好序的序列中对比
            var j = i - 1
            while j >= 0 && temp < array[j]{
                //             将当前元素后移一个位置
                array[j+1] = array[j]
                j -= 1
            }
            //        将temp放到j+1这个位置上
            array[j+1] = temp
        }
        return array
    }
    
    /*
     注解：
     1:外层i遍历，表示取出数组的第i位元素。例如:原数组[1,2,5,4]取出第i=1位的元素2，此时这个元素2可以理解为被取出来，使原数组变成[1,_,5,4]。
     2:内层j循环，因为i的左边已经有序，所以根据第i的元素tmp和i左边的元素j进行判断，并根据返回结果插入合适的位置。
     */
    
    //选择排序（不稳定）
    //选择排序(Selection Sort)是在一个待排序的序列中取出最小(或最大)的元素，然后放在已排好序的序列最后。
    
    func selectSort(_ array: inout [Int]) -> [Int]?{
        for i in 0..<array.count {
            //        记录最小值的下标
            var k = i
            //        标记当前值为最小值
            var min = array[k]
            
            for j in (i+1)..<array.count{
                //            判断当前无序数组中的最小值
                if min > array[j]{
                    min = array[j]
                    //                k指向最小值下标
                    k = j
                }
            }
            
            //若当前元素为其本身,不做交换
            if k != i{
                let temp = array[i]
                array[i] = array[k]
                array[k] = temp
            }
            
        }
        return array
    }
    
    /*
     注解：
     
     1:外层i循环首先会记录下标并赋值给k。
     
     2:内层j循环通过遍历i的元素，并判断其大小，取出最小值下标，最后交换其位置，完成排序。
     
     选择排序在时间复杂度上和冒泡、插入排序一样都是O(n^2)，但是其交换次数少于冒泡算法。
     */
    
    //    堆排序（不稳定） 平均时间复杂度均为O(nlogn)
    //    堆排序(Heap Sort)是利用堆这种数据结构而设计的一种排序算法，是选择排序的一种。通过调整堆结构，将堆的顶部元素（即数组第0位元素）与末尾的元素进行交换，调整后将末尾元素固定，然后继续调整新的堆结构，每次调整固定一个元素，遍历结束后从而达到排序的效果。
    /*
     堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
     */
    
    func heapSort(_ array: inout [Int]) -> [Int]? {
//       构建大顶堆 从最后一个非叶子节点倒序遍历
        for i in (0...(array.count/2 - 1)).reversed() {
//            从第一个非叶子节点从下至上 从右至左调整结构
            adjustHeap(&array, i: i, length: array.count)
        }
        
//        上面已将输入数组调整成堆结构
        for j in (1...(array.count - 1)).reversed() {
//            堆顶元素与末尾元素进行交换
            array.swapAt(0, j)
            adjustHeap(&array, i: 0, length: j)
        }
        
        return array
        
    }
    
    func adjustHeap(_ array: inout [Int],i: Int,length:Int) {
        var j = i
//      取出当前元素i
        let temp = array[j]
        
        var k = 2*i+1
        while k < length {
//            左子节点小于右子节点
            if(k+1 < length && array[k] < array[k+1]){
//                取到右子节点
                k+=1
            }
            if (array[k] > temp){
//              如果子节点大于父节点 将子节点赋值给父节点（不用进行交换）
                array[j] = array[k]
                j = k
            }else{
                break
            }
            k = k*2+1
            
        }
//        将temp值放到最终的位置
        array[j] = temp
        
    }
    
    /*
     注解：
     1:在i循环方法中，首先将原始入参数组调用adjustHeap方法进行大顶堆的构建，目的是方便下面循环中堆顶与末尾元素进行交换操作。进行该遍历操作时需要注意该遍历采用的是倒序遍历的方式，即从最后一个非叶子结点开始。
     2:j循环中，对已构建好大堆顶的数组进行堆顶元素与末尾元素的交换，并固定新的末尾元素，遍历结束即得到排序好的数组。
     3: adjustHeap方法，是取根节点的下标i元素与其左右子节点对应元素进行大小比较，将最大值赋给根节点。
     */
    
//    归并排序（稳定）
    //    归并操作(Merge Sort)是建立在归并操作的排序算法，是将需要排序的序列进行拆分，拆分成每一个单一元素。这时再按每个元素进行比较排序，两两合并，生成新的有序序列。再对新的有序序列进行两两合并操作，直到整个序列有序。
//    归并排序在性能上会明显优于前面几种排序方法，时间复杂度为O(nlogn)
    
    func mergeSort(_ array: [Int]) -> [Int] {
        //初始化辅助数组 默认数据0
        var helper = Array(repeating: 0, count: array.count)
        var array = array
        mergeSort(&array, &helper, 0, array.count - 1)
        return array
        
    }
    
    func mergeSort(_ array: inout [Int], _ helper: inout [Int], _ low: Int, _ high: Int) {
        //判断是否拆分至单一元素
        guard low < high else {
            return
        }
        //使用二分法对入参数组进行拆分
        let middle = (high - low)/2 + low
        mergeSort(&array, &helper, low, middle)
        mergeSort(&array, &helper, middle + 1, high)
        //合并数组
        merge(&array, &helper, low, middle, high)
    }
    
    func merge(_ array: inout [Int], _ helper: inout [Int], _ low: Int, _ middle: Int, _ high: Int) {
        //辅助数组接收 分割范围内的元素
        for i in low...high {
            helper[i] = array[i]
        }
        //helperLeft为分割部分左边的元素下标,helperRight为分割部分右边的元素下标，初始化时默认是第0位元素下标。
        var helperLeft = low, helperRight = middle + 1
        //合并后新序列的下标
        var current = low
        //判断子序列是否越界
        while helperLeft <= middle && helperRight <= high {
            //判断分割成的子序列元素大小
            if helper[helperLeft] <= helper[helperRight] {
                //对入参array数组进行赋值
                array[current] = helper[helperLeft]
                //判断左序列的下一位元素
                helperLeft += 1
                
            } else {
                //同上
                array[current] = helper[helperRight]
                //判断右序列的下一位元素
                helperRight += 1
            }
            //新序列下标向右移动
            current += 1
        }
        //不满足middle>=helperLeft return
        guard middle - helperLeft >= 0 else {
            return
        }
        
        for i in 0...middle - helperLeft {
            //将元素补齐
            array[current + i] = helper[helperLeft + i]
        }
    }
    
    
    /*
     注解：
     1:首先初始化辅助数组helper，和需要排序的数组一起传入**mergeSort(::::)**方法。
     2:**mergeSort(::::)**通过递归，将入参数组进行拆分，直至为单一元素。
     3: merge方法根据所传下标参数，对数组array进行拆分。并借助辅助helper数组完成array数组的排序操作。
     归并排序理解起来会比前几种排序方法更难一些，学习时理解了归并排序的核心思想：拆分->排序->合并，再结合代码，就能事半功倍。
     */
    
//    快速排序（不稳定）
//    快速排序(Quick Sort)是一种高效的排序方法，它利用了归并排序的思想，将需要排列的数组拆分成每一小部分，然后让每一小部分进行排序、合并，最后得到完整的排序序列。
    
    func quickSort(_ array: [Int]) -> [Int] {
//        判断是否为单一元素
        guard array.count > 1 else{
            return array
        }
        
//       取出数组中间下标元素
        let pivot = array[array.count/2]
//        用到了函数式方法filter 过滤元素
        let left = array.filter{$0 < pivot}
        let middle = array.filter{$0 == pivot}
        let right = array.filter{$0 > pivot}
        
        //递归 对新数组进行合并
        return quickSort(_:left) + middle + quickSort(_:right)
        
    }
    
    
    
//    桶排序（稳定）
    //    桶排序 (Bucket Sort)的工作原理是将数组分到n个相同的大小的子区间，每个子区间就是一个桶，然后将输入数组中的元素一一对应，放入对应子区间内的桶中。最后遍历每个桶，依次输入每个桶中对应装的数据即可。因为桶的顺序是有序的，所以只要从第一个桶开始遍历，得到的结果也就是有序的数组。
    
    func bucketSort(_ array: inout [Int]) -> [Int]? {
        
        //求出桶的数量
        let max = array.max()
        let min = array.min()
        let bucketCount = max! - min!
        
        //创建桶数组，桶个数=最大值-最小值+1，默认初值都为0。
        var bucket = Array(repeating: 0, count: bucketCount + 1)
        //遍历入参数组元素，并给桶做上标记
        for num in array {
            //数组元素减去最小值，指向桶数组下标
            let index = num - min!
            //将元素出现次数打上标记，每次+1
            bucket[index] += 1
        }
        //记录新数组下标
        var arrayIndex = 0
        
        //对桶内元素进行遍历
        for i in 0..<bucket.count {
            //取出每个桶的标记值
            var j = bucket[i]
            //当桶内有值，根据标记的次数依次减1，添加到数组中
            while j > 0 {
                array[arrayIndex] = i + min!
                j-=1
                arrayIndex+=1
            }
        }
        return array
    }
    
/*
     注解：
     1:输入为整数数组，所以先求出数组中的最大值和最小值，求出桶的数量，然后创建默认值为0的桶数组。
     2:遍历入参数组array中的元素，并放入对应区间的桶中。
     3:遍历桶数组，取出每个桶中的标记值。将桶中大于0的标记值所对应的区间值加入到数组中，返回数组。
     桶排序的复杂度为O(n),也是上面所有排序方法中性能最好的，逻辑也比较简单。另外关于桶排序中有一点需要注意的是，创建的桶个数尽量应从最小值开始创建，如果只以最大值创建桶的数量，会造成不必要的内存开销。
     */
    

}
